package com.chj.gaoji.class14;

import java.util.HashMap;
import java.util.Map;

public class Code02_LongestConsecutive {
	public static int longestConsecutive(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int max = 1;
		// 不区分开头和结尾
		// (key, value)
		// key所在的连续区域，这个区域一共有几个数，value
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < arr.length; i++) { // 从左到右遍历每一个数字
			if (!map.containsKey(arr[i])) {
				map.put(arr[i], 1); // arr[i] ~ arr[i]
				if (map.containsKey(arr[i] - 1)) { // 是否有arr[i] - 1的结尾
					max = Math.max(max, merge(map, arr[i] - 1, arr[i]));
				}
				if (map.containsKey(arr[i] + 1)) { // 是否有arr[i] + 1的开头
					max = Math.max(max, merge(map, arr[i], arr[i] + 1));
				}
			}
		}
		return max;
	}

	public static int merge(HashMap<Integer, Integer> map, int preRangeEnd, int curRangeStart) {
		int preRangeStart = preRangeEnd - map.get(preRangeEnd) + 1;
		int curRangeEnd = curRangeStart + map.get(curRangeStart) - 1;
		int len = curRangeEnd - preRangeStart + 1;
		map.put(preRangeStart, len);
		map.put(curRangeEnd, len);
		return len;
	}

	public static int longestConsecutive02(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}

		int max = 1;
		int maxn = 1;
		int minn = 1;
		// 不区分开头和结尾
		// (key, value)
		// key所在的连续区域，这个区域一共有几个数，value
		HashMap<Integer, Integer> smap = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> emap = new HashMap<Integer, Integer>();
		for (int i = 0; i < arr.length; i++) { // 从左到右遍历每一个数字
			if (!smap.containsKey(arr[i])) {

				smap.put(arr[i], arr[i]); // arr[i] ~ arr[i]
				emap.put(arr[i], arr[i]);
				if (emap.containsKey(arr[i] - 1)) { // 是否有arr[i] - 1的结尾
					maxn = Math.max(maxn, arr[i]);
					minn = Math.min(minn, arr[i]);
					max = Math.max(max, merge02(smap, emap, arr[i] - 1, arr[i]));
				}
				if (smap.containsKey(arr[i] + 1)) { // 是否有arr[i] + 1的开头
					maxn = Math.max(maxn, arr[i]);
					minn = Math.min(minn, arr[i]);
					max = Math.max(max, merge02(smap, emap, arr[i], arr[i] + 1));
				}
			}
		}

		if (emap.containsKey(maxn) && smap.containsKey(minn)) {
			max = emap.get(maxn) - smap.get(minn) + 1;
		}

		return max;
	}

	public static int merge02(HashMap<Integer, Integer> smap, HashMap<Integer, Integer> emap, int preRangeEnd,
			int curRangeStart) {
//		int preRangeStart = preRangeEnd - map.get(preRangeEnd) + 1;
//		int curRangeEnd = curRangeStart + map.get(curRangeStart) - 1;
//		int len = curRangeEnd - preRangeStart + 1;
//		map.put(preRangeStart, len);
//		map.put(curRangeEnd, len);

		smap.put(preRangeEnd, smap.get(preRangeEnd));
		smap.put(curRangeStart, smap.get(preRangeEnd));

		emap.put(preRangeEnd, emap.get(curRangeStart));
		emap.put(curRangeStart, emap.get(curRangeStart));
		int len = emap.get(curRangeStart) - smap.get(preRangeEnd) + 1;

		return len;
	}

	public static class UnionFind {
		Map<Integer, Integer> parents;

		public UnionFind(int[] arr) {
			parents = new HashMap<>();
			for (int i : arr) {
				parents.put(i, i);
			}
		}

		public Integer find(int x) {
			if (!parents.containsKey(x))
				return null;
			int t = parents.get(x);
			if (x != t)
				parents.put(x, find(t));
			return parents.get(x);
		}

		public boolean union(int x, int y) {
			Integer rootX = find(x), rootY = find(y);
			if (rootX == null || rootY == null)
				return false;
			if (rootX.equals(rootY))
				return false;
			parents.put(rootX, rootY);
			return true;
		}
	}

	public static int longestConsecutive03(int[] nums) {
		if (nums.length == 0)
			return 0;
		UnionFind u = new UnionFind(nums);
		for (int num : nums) {
			u.union(num, num + 1);
		}
		int max = 1;
		for (int num : nums) {
			max = Math.max(max, u.find(num) - num + 1);
		}
		return max;
	}

	public static int longestConsecutive04(int[] nums) {
		Map<Integer, Integer> map = new HashMap<>();
		int max = 0;
		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i]))
				continue;
			int left = map.getOrDefault(nums[i] - 1, 0);
			int right = map.getOrDefault(nums[i] + 1, 0);
			int len = left + right + 1;
			max = Math.max(max, len);
			map.put(nums[i], len);
			map.put(nums[i] - left, len);
			map.put(nums[i] + right, len);
		}
		return max;
	}

//	作者：outvoker-c
//	链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/javaliang-chong-fang-fa-luo-ji-qing-xi-yi-kan-jiu-/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static int longestConsecutive06(int[] nums) {
		if (nums == null || nums.length == 0)
			return 0;
		Map<Integer, Integer[]> map = new HashMap<>();
		int maxVal = 0;
		for (int i : nums) {
			if (map.containsKey(i))
				continue;
			Integer[] ints = null;
			Integer[] high = i < Integer.MAX_VALUE ? map.get(i + 1) : null;
			Integer[] low = i > Integer.MIN_VALUE ? map.get(i - 1) : null;
			if (high != null && low != null) {
				ints = new Integer[] { low[0], high[1] };
			} else if (high == null && low != null) {
				ints = low;
				ints[1] = i;
			} else if (high != null && low == null) {
				ints = high;
				ints[0] = i;
			} else if (high == null && low == null) {
				ints = new Integer[] { i, i };
			}
			int len = ints[1] - ints[0] + 1;
			// System.out.println("arr:" + ints[0] + " " + ints[1] + " len " + len);
			if (maxVal < len) {
				maxVal = len;
			}
			map.put(ints[0], ints);
			if (!ints[1].equals(ints[0]))
				map.put(ints[1], ints);
			if (!map.containsKey(i))
				map.put(i, null);
		}
		return maxVal;
	}

//	作者：shawn-146
//	链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/onfu-za-du-wan-cheng-yi-ge-mapsetzu-gou-si-lu-zu-g/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
//		{
//			int[] arr = { 100, 4, 200, 1, 3, 2 };
//			System.out.println(longestConsecutive(arr));
//		}

		{
			int[] arr = { 100, 4, 200, 1, 3, 2 };
			System.out.println(longestConsecutive06(arr));
			System.out.println(100 < Integer.MAX_VALUE);
		}

//		{
//			int[] arr = { 9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6 };
//			System.out.println(longestConsecutive03(arr));
//		}
	}
}
